
package com.sort;

import utils.CreateArr;

/**
 * (4)快速排序:从小到大排序
 * 1.选定一个元素
 * 2.对其他元素进行遍历,使得一部分的区域都小于这个元素的值,而另一部分则大于等于它,但这两个部分不需要有序
 * 3.对这两部分再进行快速排序的步骤,知道最后有序.
 */
public class QuickSort {


    static int[] quickSort(int[] arr) {
        return __quickSort_3(arr, 0, arr.length - 1);
    }

    /*优化4 : 三路快速排序*/
    /*以k为标识,将数组分为三个部分,一部分 <k ,一部分 =k , 一部分 >k .
     *在双路快速排序的基础上,通过索引 i 进行整个数组的遍历,
     *  如果 arr[i] < i,那么就把它加入到 <k 的部分(arr[left + 1 ... lt]),
     *  如果 arr[i] = i,那么就把它加入到 =k 的部分(arr[lt + 1 ... gt - 1])
     *  如果 arr[i] > i,那么就把它加入到 >k 的部分(arr[gt ... right])
     *得到三个部分之后,将 k 放回应该在的位置,即与 arr[lt] 交换位置
     *现在得到三个部分:
     *  >arr[left ... lt - 1] 的部分都是 小于k 的,继续递归的快排
     *  >arr[lt ... gt] 的部分都是 =k 的,不需要动了
     *  >arr[gt ... right] 的部分都是 >k 的,继续递归的快排
     *
     *  (当数组中重复的数字相当多的时候,优势会更加明显)
     * */
    private static int[] __quickSort_3(int[] arr, int left, int right) {
        if (right - left <= 10) {
            //对小于10个元素的部分进行插入排序,以提高效率
            InsertionSort.insertionSort_3(arr);
            return arr;
        }
        int k = arr[(int) (Math.random() * (right - left) + left)];  //使得k随机生成
        //将k移动到最左侧
        int temp = k;
        k = arr[left];
        arr[left] = temp;

        int lt = left;  //arr[left + 1 ... lt] < v
        int gt = right + 1; //arr[gt ... right] > v
        int i = left + 1;   //arr[lt + 1 ... i) = v

        while (i < gt) {
            if (arr[i] < k) {
                //小于k , 此时交换 arr[i] 与 arr[lt + 1]
                int t = arr[i];
                arr[i] = arr[lt + 1];
                arr[lt + 1] = t;
                lt++;
                i++;
            } else if (arr[i] > k) {
                //大于k , 此时交换 arr[i] 与 arr[gt - 1]
                int t = arr[i];
                arr[i] = arr[gt - 1];
                arr[gt - 1] = t;
                gt--;
            } else {
                //=k , 此时不变,让它保持原位置
                i++;
            }
        }

        //整个数组分割为三个部分之后,这时要把 k (arr[left]) 放置到 =k 的那部分中
        temp = arr[left];
        arr[left] = arr[lt];
        arr[lt] = temp;
        __quickSort_3(arr, left, lt - 1);
        __quickSort_3(arr, gt, right);

        return arr;
    }

    //对 arr[left .... right] 的部分进行操作
    private static int[] __quickSort(int[] arr, int left, int right) {

//(优化)        if (right <= left) {
//(优化)            return arr;
//(优化)        }


        /*优化1: 上面的if代码块*/
        /*在底层时近乎有序的概率很大,此时可以使用这种情况下效率较高的插入排序*/
        if (right - left <= 10) {
            InsertionSort.insertionSort_3(arr);
            return arr;
        }


//(优化)        int k = arr[left];  //选定第一个元素,作为切分两个部分的标识

        /*优化2*/
        /*如果整个数组近乎有序,那么选择第一个元素作为切分标识会导致整个切分近乎成为列表形式,时间复杂度退化为 O( n * n )
         *如果随机选取,则会使整个排序的数学期望为 O( n * log n) **/
        int k = arr[(int) (Math.random() * (right - left) + left)];  //使得k随机生成
        //将k移动到最左侧
        int temp = k;
        k = arr[left];
        arr[left] = temp;

        int j = left;   //作为标识 小于k 的那部分的结尾的下标
        //现在通过遍历整个数组,需要使得 arr[left ... j] 都 小于k ,而 arr[j+1 ... right] 都 大于k ;
        for (int i = left + 1; i <= right; i++) {
            if (arr[i] >= k) {
                //如果发现 arr[i] >= k ,证明它属于第二部分,就让它待在遍历过的末尾,不要管它就好

            } else {
                //如果发现 arr[i] < k ,证明它属于第一部分,需要把它(arr[i]的元素值)与 arr[j + 1] 交换位置 ,并且将 j++,这样就保证这两部分满足规则
                int temp_1 = arr[i];
                arr[i] = arr[j + 1];
                arr[j + 1] = temp_1;
                j++;
            }
        }

        //遍历结束后,把作为标识的 k 恢复到原数组中,即将 k 的元素值与 arr[j] 交换位置
        temp = arr[left];
        arr[left] = arr[j];
        arr[j] = temp;

        //递归的对两个部分都进行遍历
        __quickSort(arr, left, j);
        __quickSort(arr, j + 1, right);
        return arr;
    }

    /*改进3:双路快速排序*/
    /*如果存在大量重复的值(比如 10个1,100个2,1000个3 随机打乱后进行排序),那么会使小于k的部分特别少,而大于等于k的部分却很多,因此需要改进
     *  此时不再从左到右的进行遍历,而是从左右两个方向从中间遍历,一部分只搜集小于k的元素,另一部分只搜集大于k的元素.
     *  当两个方向都遇到不属于自己这部分的元素时,交换它们两个元素的位置即可.直到这两部分相遇,然后将k放回数组中,进行递归.
     * */
    private static int[] __quickSort_2(int[] arr, int left, int right) {
        if (right - left <= 10) {
            InsertionSort.insertionSort_2(arr);
            return arr;
        }
        int k = arr[(int) (Math.random() * (right - left) + left)];  //使得k随机生成
        //将k移动到最左侧
        int temp = k;
        k = arr[left];
        arr[left] = temp;
        int i = left + 1;   //使得 i 扫过的部分 <= k
        int j = right;  //使得 j 扫过的部分 >= k
        //现在需要使arr[left + 1 ... j] <= k , arr[j + 1 ... right] >= k
        //因为无法找到 i 与 j 暂停的具体位置,因此只能通过while的条件来进行判断
        while (true) {
            while (i <= right && arr[i] < k) {
                i++;
                //退出while时表明 arr[i] 不属于 <k 的部分
            }
            while (j >= left + 1 && arr[j] > k) {
                j--;
                //退出while时表明 arr[j] 不属于 >k 的部分
            }
            //退出整个循环的条件,表明当前部分排序完成
            if (i > j) {
                break;
            }
            //交换 arr[i] 与 arr[j] 的位置,使得它们回归属于它们的位置
            int temp_1 = arr[j];
            arr[j] = arr[i];
            arr[i] = temp_1;
            i++;
            j--;
        }

        //完成排序后,交换 k 与 arr[j] 的位置
        temp = arr[j];
        arr[j] = arr[0];
        arr[0] = temp;

        __quickSort_2(arr, left, j);
        __quickSort_2(arr, j + 1, right);
        return arr;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int arr[] = quickSort(CreateArr.createRandomInt(200, 0, 100000));
        long end = System.currentTimeMillis();
        System.out.println("\n" + (end - start));
        System.out.print("\n排序后 : ");
        for (int i : arr) {
            System.out.print(" " + i);
        }
    }


}
